1. Field of the Invention
This invention relates generally to communications systems using multidimensional signaling. More particularly, this invention relates to a sub-optimal minimum distance decoder and method of decoding that outperforms known sub-optimal decoders used in multiple-input multiple-output (MIMO) communication systems.
2. Description of the Prior Art
Multiple-input multiple-output (MIMO) communication systems provide gains in capacity and quality compared to single-input single-output (SISO) communication systems. Examples of MIMO systems include but are not limited to: 1. A narrowband wireless communication system employing multiple-antenna at the transmitter and/or receiver; 2. A broadband communication system employing orthogonal frequency division multiplexing (OFDM); 3. A time division multiple access system; 4. Any multiuser communication system; and/or 5. Any combination of 1-4 above.
These systems commonly employ a block structure where the transmitter (here transmitter refers to the collection of SISO transmitters) sends multidimensional symbol information. This multidimensional symbol could, but is not limited to, be represented by a vector or matrix. The multidimensional symbol might represent one or more coded or uncoded SISO data symbols. The receiver (here receiver refers to the collection of SISO receivers) receives one of more copies of this transmitted symbol vector. The performance of the entire communication system hinges on the ability of the receiver to find reliable estimates of the multidimensional symbol that was transmitted.
Definitions
As used herein, bolded capitol symbols, such as H, represent matrices.
As used herein, bolded lower-case symbols, such as s, represent vectors.
As used herein, T denotes matrix transposition.
As used herein, * denotes the matrix conjugate transpose operation.
As used herein, −1 denotes the matrix inverse operation.
As used herein, if W is a matrix, Wm denotes the mth column of W.
As used herein, if W is a matrix, (WT)m denotes the mth row of W.
As used herein, if v is a vector, ∥v∥2, denotes the 2-norm of v.
As used herein, if Q(•) represents the symbol slicing function, it will be assumed to slice both single symbols and multi-dimensional symbol vectors.
As used herein, IM represents the M by M identity matrix.
As used herein, OM×N represents the M by N matrix of zeros.
As used herein, if A and B are sets, then A|B is the set of all elements in A that are not in B.
For MIMO systems such as, but not limited to, the ones discussed herein above, the received signal can be written in the formyk=ΣnHnsk−n+v  (1)where Hn is an Mr by Mt matrix of complex gains, sk is the Mt-dimensional symbol vector transmitted at time k, and v is a Mt-dimensional vector of additive noise. In narrowband wireless systems where the symbol period is much larger than the RMS delay spread as well as OFDM systems, each SISO channel is often modeled as a single-tap complex gain. In this case equation (1) simplifies toyk=Hsk+v  (2)where H is now an Mr by Mt matrix of complex numbers and Hsk is the matrix product of H and sk.
The receiver must estimate the symbol matrix S=[s1 . . . sT] in order to facilitate reliable communication. Examples, but by no means the only examples, of multidimensional symbols could be space-time codes where T>1 or spatial multiplexing systems with T=1 and independent SISO modulation on each transmit stream. If v were not present and H were invertible, this would simply be the problem of inverting H. The presence of noise however, increases the difficulty of estimating S. The receiver is generally assumed to have some estimate of H available to it. As well, the symbol matrix S is assumed to be chosen from a finite set C of possible multidimensional symbols.
The optimal solution in the sense of minimizing the probability of symbol error has been shown to be the maximum aposterior (MAP) decoder which is equivalent in the case of equiprobable symbol transmissions to a maximum likelihood (ML) decoder. The ML decoder attempts to find S, the symbol matrix, by using the symbol matrix {tilde over (S)} that maximizes p({tilde over (S)}|y1, . . . , yT) where p(•|y1, . . . , yT) is the conditional probability density function (pdf) of sk given y1, . . . , yT. In real-time communications systems, however, this type of decoder is overly computationally complex. We will call decoders that search over an entire set V and decode to the multidimensional symbol {tilde over (S)} that minimize some sort of metric minimum distance (MD) decoders. Examples of MD decoders include MAP and ML decoding with V=C.
Algorithms have been proposed that are computationally easier than ML decoding in order to overcome this computational hurdle. Algorithms that perform some form of reduced complexity decoding will be referred to herein as sub-optimal decoders. An example of this type of decoder is successive interference cancellation (SIC). A receiver using SIC decodes each symbol within the symbol vector one at a time. After a symbol is decoded, its approximate contribution to the received vector is subtracted in order to improve the estimate of the next symbol within the symbol vector.
An example of an SIC receiver is the ordered iterative minimum mean squared error (IMMSE) receiver. With a single-tap channel, the receive signal is given by equation (2) above. Letting sk=[s1 s2 . . . sMr]T, the ordered IMMSE operates using the following steps, letting yk,0=yk, D0={1, 2, . . . , Mt}, and Hk(0)=H.
            1.      ⁢                          ⁢      Set      ⁢                          ⁢      m        =    0.                      2.        ⁢                                  ⁢        Compute        ⁢                                  ⁢                  W          m                    =                                                  (                                                                    H                    k                                                                  (                        m                        )                                            +                                                        ⁢                                      H                    k                                          (                      m                      )                                                                      +                                  ρI                                      M                                          t                      -                      m                                                                                  )                                      -              1                                ⁢                                    H              k                                                (                  m                  )                                +                                      .                                                  ⁢            3.                    ⁢                                          ⁢          Let          ⁢                                          ⁢          n                =                              arg            ⁢                                                  ⁢                                          min                                  i                  ∈                                      D                    0                                                              ⁢                                                                                                                                                                  (                                                      W                                                                                          (                                m                                )                                                            ⁢                              T                                                                                )                                                i                                                                                    2                                    .                                                                          ⁢                  4.                                ⁢                                                                  ⁢                Set                ⁢                                                                  ⁢                                                      s                    ~                                                        k                    ,                                          n                      ·                                                                                                    =                                                                      Q                  ⁡                                      (                                                                                            y                                                      k                            ,                            m                                                    T                                                ⁡                                                  (                                                      W                                                                                          (                                m                                )                                                            ⁢                              T                                                                                )                                                                    i                                        )                                                  .                                                                  ⁢                5.                            ⁢                                                          ⁢              Set              ⁢                                                          ⁢                              y                                  k                  ,                                      m                    +                    1                                                                        =                                          y                                  k                  ,                  m                                            -                                                H                                      k                    ,                    n                                                        (                    m                    )                                                  ⁢                                                      s                    ~                                                        k                    ,                    n                                                                                            ,                  D                  m          +          1                    =                        D          m                ⁢        \        ⁢                  {          n          }                      ,    and                      ⁢                  H        k                  (                      m            +            1                    )                    =                                                                  [                                                      H                                          k                      ,                      1                                                              (                                              m                        +                        1                                            )                                                        ⁢                                      H                                          k                      ,                      2                                                              (                                              m                        +                        1                                            )                                                        ⁢                  …                  ⁢                                                                          ⁢                                      H                                          k                      ,                                              n                        -                        1                                                                                    (                                              m                        +                        1                                            )                                                        ⁢                                      0                                          M                                              r                        ×                        1                                                                              ⁢                                      H                                          k                      ,                                              n                        +                        1                                                                                    (                                              m                        +                        1                                            )                                                        ⁢                  …                  ⁢                                                                          ⁢                                      H                                          k                      ,                                              M                        t                                                                                    (                                              m                        +                        1                                            )                                                                      ]                            .                                                          ⁢              6.                        ⁢                                                  ⁢            Repeat            ⁢                                                  ⁢            steps            ⁢                                                  ⁢            1            ⁢                          -                        ⁢            5            ⁢                                                  ⁢                          fo              ⁢              r                        ⁢                                                  ⁢            m                    <                                                    M                t                            .                                                          ⁢              7.                        ⁢                                                  ⁢            Set            ⁢                                                  ⁢            the            ⁢                                                  ⁢            decoded            ⁢                                                  ⁢            symbol            ⁢                                                  ⁢            vector            ⁢                                                  ⁢            to            ⁢                                                  ⁢                                          s                ~                            k                                      =                                            [                                                                    s                    ~                                                        k                    ,                    1                                                  ⁢                                                                  ⁢                                                      s                    ~                                                        k                    ,                    2                                                  ⁢                                                                  ⁢                …                ⁢                                                                  ⁢                                                      s                    ~                                                        k                    ,                                          M                      1                                                                                  ]                        T                    .                    Regarding the above algorithm, it is important to note that
  H      k    ,    i        (          m      +      1        )  denotes the ith row of the matrix Hk(m+1) (time k and iteration m+1). Another example is the zero-forcing decoder which decodes to the symbol {tilde over (s)}k=Q(H−1yk). This decoder is usually considered the worst performing and least complex of the sub-optimal decoders.
Sub-optimal techniques unfortunately differ in diversity order from ML decoding (i.e. the asymptotic slope of the average probability of bit error curve). They essentially trade reduced complexity for reduced performance.
In view of the foregoing, it is both advantageous and desirable to find other low complexity schemes that, while still being low complexity, perform closer to an ML decoder.